package quwei;
//2.4会议安排
import java.util.Scanner;

class Meet{
    int beg;                               //会议的开始时间
    int end;                               //会议的结束时间
    int num;                               //记录会议的编号
}

class SetMeet{
    private int n;                         //会议总数
    private int answer;                    //最大的安排会议总数
    private int last;                      //记录被选中会议的结束时间
    Meet[] meet=new Meet[1000];               //存放会议对象的数组

    /*读入数据*/
    public void init() {
        Scanner scanner=new Scanner(System.in);
        System.out.println("输入会议总数：");
        n=scanner.nextInt();    
        System.out.println("输入会议的开始时间和结束时间，以空格分开：");
        for(int i=0;i<n;i++) {
            meet[i]=new Meet();            //初始化对象
            meet[i].beg=scanner.nextInt();
            meet[i].end=scanner.nextInt();
            meet[i].num=i+1;
        }
        scanner.close();
    }

    public void solve() {
        selectionSort(meet);                                 //对会议按照结束时间由小到大排序
        System.out.println("排完序的会议时间如下：");
        System.out.println("会议编号  开始时间  结束时间");
        for(int i=0;i<n;i++) 
            System.out.println("   "+meet[i].num+"       "+meet[i].beg+"       "+meet[i].end);
        System.out.println();
        System.out.println("选择会议的过程：");
        System.out.println(" 选择第"+meet[0].num+"个会议");  //选中了第一个会议
        answer=1;
        last=meet[0].end;

        for(int i=1;i<n;i++) {                               //依次检查每个会议
            if(meet[i].beg>=last) {                          //如果会议i开始的时间大于等于最后一个选中的会议的结束时间
                System.out.println(" 选择第"+meet[i].num+"个会议");
                answer++;                                    //可安排的会议总数+1
                last=meet[i].end;                            //更新last为最后一个选中会议的结束时间             
            }
        }
        System.out.println("最多可以安排"+answer+"个会议");
    }

    public void selectionSort(Meet[] array){                 //运用选择排序对会议按结束时间由小到大排序

        Meet temp=new Meet();
        for(int i=0;i<n-1;i++){      
            for(int j=i+1;j<=n-1;j++){ 
                 if(array[i].end>array[j].end){          
                    temp = array[i];                          //要将类的所有成员变量进行换位置，因为值是相互对应的
                    array[i] = array[j];
                    array[j] = temp;
                 }
            }
        }
    }

}

public class Test2_4 {
    public static void main(String[] args) {
        SetMeet sm=new SetMeet();                             //创建对象
        sm.init();                                            //读入数据
        sm.solve();                                           //贪心算法求解
    }   
}
